class Solution:
    # DP 思路：
    #    P(i,j) 表示 [i,j] 子串是否为回文
    # 状态转移方程：
    #    P(i,j) = P(i+1,j-1) and (s[i]==s[j])
    #    P(i,i) = true
    #    P(i,i+1) = (s[i]==s[j])
    # 维护一个 nxn 的表格即可
    # 复杂度：O(n^2), O(n^2)
    
    # Better: 中心扩展算法
    # 复杂度：O(n^2), O(1)
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start:end+1]

    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
